\ifx\wholebook\relax \else
% ------------------------

\documentclass{article}
%------------------- Other types of document example ------------------------
%
%\documentclass[twocolumn]{IEEEtran-new}
%\documentclass[12pt,twoside,draft]{IEEEtran}
%\documentstyle[9pt,twocolumn,technote,twoside]{IEEEtran}
%
%-----------------------------------------------------------------------------
%\input{../../../common.tex}
\input{../../../common-en.tex}

\setcounter{page}{1}

\begin{document}

%--------------------------

% ================================================================
%                 COVER PAGE
% ================================================================

\title{AVL tree}

\author{Larry~LIU~Xinyu
\thanks{{\bfseries Larry LIU Xinyu } \newline
  Email: liuxinyu95@gmail.com \newline}
  }

\maketitle
\fi

\markboth{AVL tree}{Elementary Algorithms}

\ifx\wholebook\relax
\chapter{AVL tree}
\numberwithin{Exercise}{chapter}
\fi

% ================================================================
%                 Introduction
% ================================================================
\section{Introduction}
\label{introduction} \index{AVL tree}

\subsection{How to measure the balance of a tree?}
Besides red-black tree, are there any other intuitive solutions of self-balancing
binary search tree? In order to measure how balancing a binary search tree is,
one idea is to compare the height of the right sub-tree and left sub-tree.
If they differs a lot, the tree isn't well balanced. Let's denote the
difference height between two children as below

\be
  \delta(T) = |R| - |L|
\ee

Where $|T|$ means the height of tree $T$, and $L$, $R$ denotes the left
sub-tree and right sub-tree.

If $\delta(T) = 0$, The tree is definitely balanced. For example, a
complete binary tree has $n=2^h-1$ nodes for height $h$. There is
no empty branches unless the leafs. Another trivial case is empty
tree. $\delta(\phi) = 0$. The less absolute value of $\delta(T)$
the more balancing the tree is.

We define $\delta(T)$ as the {\em balance factor} of a binary search
tree.

% ================================================================
% Definition
% ================================================================
\section{Definition of AVL tree}
\index{AVL tree!definition}

An AVL tree is a special binary search tree, that all sub-trees
satisfying the following criteria.

\be
  |\delta(T)| \leq 1
\ee

The absolute value of balance factor is less than or equal to 1, which
means there are only three valid values, -1, 0 and 1. Figure \ref{fig:avl-example} shows an example AVL tree.

\begin{figure}[htbp]
   \centering
   \includegraphics[scale=0.5]{img/avl-example.ps}
   \caption{An example AVL tree} \label{fig:avl-example}
\end{figure}


Why AVL tree can keep the tree balanced? In other words, Can this definition
ensure the height of the tree as $O(\lg n)$ where $n$ is the number of
the nodes in the tree? Let's prove this fact.

For an AVL tree of height $h$, The number of nodes varies. It can have at
most $2^h-1$ nodes for a complete binary tree. We are interesting about
how many nodes there are at least. Let's denote the minimum number of nodes
for height $h$ AVL tree as $N(h)$. It's obvious for the trivial cases
as below.

\begin{itemize}
\item For empty tree, $h=0$, $N(0)=0$;
\item For a singleton root, $h=1$, $N(1)=1$;
\end{itemize}

What's the situation for common case $N(h)$? Figure \ref{fig:N-h-relation}
shows an AVL tree $T$ of height $h$. It contains three part, the root node,
and two sub trees $L, R$. We have the following fact.

\be
  h= max(|L|, |R|) + 1
\ee

We immediately know that, there must be one child has height $h-1$. According
to the definition of AVL tree, we have
$||L|-|B|| \leq 1$. This leads to the fact that the height of
other tree can't be lower than $h-2$, So the total number of the nodes
of $T$ is the number of nodes in both children plus 1 (for the root node).
We exclaim that.

\be
  N(h) = N(h-1) + N(h-2) + 1
  \label{eq:Fibonacci-like}
\ee

\begin{figure}[htbp]
   \centering
   \includegraphics[scale=0.5]{img/Nh-lvr.ps}
   \caption{An AVL tree with height $h$, one of the sub-tree with height $h-1$, the other is no less than $h-2$} \label{fig:N-h-relation}
\end{figure}

This recursion reminds us the famous Fibonacci series. Actually we can
transform it to Fibonacci series by defining $N'(h) = N(h)+1$. So equation
(\ref{eq:Fibonacci-like}) changes to.

\be
  N'(h) = N'(h-1) + N'(h-2)
\ee

\begin{lemma}
\label{lemma:N-phi}
Let $N(h)$ be the minimum number of nodes for an AVL tree with
height $h$. and $N'(h) = N(h) + 1$, then
\be
  N'(h) \geq \phi^h
\ee

Where $\phi = \frac{\sqrt{5}+1}{2}$ is the golden ratio.
\end{lemma}

\begin{proof}
For the trivial case, we have
\begin{itemize}
\item $h=0$, $N'(0) = 1 \geq \phi^0 = 1$
\item $h=1$, $N'(1) = 2 \geq \phi^1 = 1.618...$
\end{itemize}

For the induction case, suppose $N'(h) \geq \phi^h$.
\[
  \begin{array}{lll}
  N'(h+1) & = N'(h) + N'(h-1) & \{Fibonacci\} \\
          & \geq \phi^h + \phi^{h-1} & \\
          & = \phi^{h-1}(\phi + 1) & \{\phi + 1 = \phi^2 = \frac{\sqrt{5}+3}{2}\} \\
          & = \phi^{h+1}
 \end{array}
\]
\end{proof}

From Lemma \ref{lemma:N-phi}, we immediately get

\be
  h \leq log_{\phi}(n+1) = log_{\phi}2 \cdot \lg (n+1) \approx 1.44 \lg (n+1)
  \label{eq:AVL-height}
\ee

It tells that the height of AVL tree is proportion to $O(\lg n)$, which
means that AVL tree is balanced.

During the basic mutable tree operations such as insertion and deletion,
if the balance factor changes to any invalid value, some fixing has
to be performed to resume $|\delta|$ within 1. Most implementations utilize
tree rotations. In this chapter, we'll show the pattern matching solution
which is inspired by Okasaki's red-black tree solution\cite{okasaki}.
Because of this modify-fixing approach, AVL tree is also a kind of
self-balancing binary search tree. For comparison purpose, we'll also
show the procedural algorithms.

Of course we can compute the $\delta$ value recursively, another option
is to store the balance factor inside each nodes, and update them
when we modify the tree. The latter one avoid computing the same value
every time.

Based on this idea, we can add one data field $\delta$ to the original
binary search tree as the following C++ code example \footnote{Some implementations store the height of a tree instead of $\delta$ as in \cite{py-avl}}.

\lstset{language=C++}
\begin{lstlisting}
template <class T>
struct node{
  int delta;
  T key;
  node* left;
  node* right;
  node* parent;
};
\end{lstlisting}

In purely functional setting, some implementation use different
constructors to store the $\delta$ information. for example in
\cite{hackage}, there are 4 constructors, \texttt{E}, \texttt{N}, \texttt{P}, \texttt{Z} defined.
\texttt{E} for empty tree, \texttt{N} for tree with negative 1 balance factor,
\texttt{P} for tree with positive 1 balance factor and \texttt{Z} for zero case.

In this chapter, we'll explicitly store the balance factor inside
the node.

\lstset{language=Haskell}
\begin{lstlisting}
data AVLTree a = Empty
               | Br (AVLTree a) a (AVLTree a) Int
\end{lstlisting}

The immutable operations, including looking up, finding the maximum
and minimum elements are all same as the binary search tree. We'll
skip them and focus on the mutable operations.

% ================================================================
%                 Insertion
% ================================================================
\section{Insertion}
\index{AVL tree!insertion}

Insert a new element to an AVL tree may violate the AVL tree property
that the $\delta$ absolute value exceeds 1. To resume it, one option
is to do the tree rotation according to the different insertion cases.
Most implementation is based on this approach

Another way is to use the similar pattern matching method mentioned by
Okasaki in his red-black tree implementation \cite{okasaki}. Inspired
by this idea, it is possible to provide a simple and intuitive
solution.

When insert a new key to the AVL tree, the balance factor of the
root may {\em changes} in range $[-1, 1]$\footnote{Note that, it doesn't mean $\delta$ is in range $[-1, 1]$, the changes of $\delta$ is in this range.}, and the height may increase
at most by one, which we need recursively use this information
to update the $\delta$ value in further level nodes. We can define
the result of the insertion algorithm as a pair of data
$(T', \Delta H)$. Where $T'$ is the new tree and $\Delta H$ is the
increment of height. Let's denote function $first(pair)$
can return the first element in a pair. We can modify
the binary search tree insertion algorithm as the following to
handle AVL tree.

\be
insert(T, k) = first(ins(T, k))
\ee

where

\be
ins(T, k) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  ((\phi, k, \phi, 0), 1) & T = \phi \\
  tree(ins(L, k), k', (R, 0), \Delta) & k < k' \\
  tree((L, 0), k', ins(R, k), \Delta) & otherwise
  \end{array}
\right.
\label{eq:ins}
\ee

$L, R, k', \Delta$ represent the left child, right child, the key and
the balance factor of a tree.

\[
  \begin{array}{l}
  L = left(T) \\
  R = right(T) \\
  k' = key(T) \\
  \Delta = \delta(T)
  \end{array}
\]

When we insert a new key $k$ to a AVL tree $T$, if the tree is
empty, we just need create a leaf node with $k$, set the balance
factor as 0, and the height is increased by one. This is the trivial
case.

If $T$ isn't empty, we need compare the key $k'$ with $k$.
If $k$ is less than the key, we recursively insert it to the left
child, otherwise we insert it into the right child.

As we defined above, the result of the recursive insertion is a
pair like $(L', \Delta H_l)$, we need do balancing adjustment as well
as updating the increment of height. Function $tree()$ is defined
to dealing with this task. It takes 4 parameters as $(L', \Delta H_l)$,
$k'$, $(R', \Delta H_r)$, and $\Delta$. The result of this function
is defined as $(T', \Delta H)$, where $T'$ is the new tree after
adjustment, and $\Delta H$ is the new increment of height which is
defined as

\be
  \Delta H = |T'| - |T|
\ee

This can be further detailed deduced in 4 cases.

\be
\begin{array}{rl}
  \Delta H & = |T'| - |T| \\
              & = 1 + max(|R'|, |L'|) - (1 + max(|R|, |L|)) \\
              & = max(|R'|, |L'|) - max(|R|, |L|) \\
              & = \left \{
                  \begin{array}{r@{\quad:\quad}l}
                  \Delta H_r & \Delta \geq 0 \land \Delta' \geq 0 \\
                  \Delta + \Delta H_r & \Delta \leq 0 \land \Delta' \geq 0 \\
                  \Delta H_l - \Delta & \Delta \geq 0 \land \Delta' \leq 0 \\
                  \Delta H_l & otherwise
                  \end{array} \right .
\end{array}
\ee

To prove this equation, note the fact that the height can't increase
both in left and right with only one insertion.

These 4 cases can be explained from the balance factor
definition that it equals to the difference from the right sub tree
and left sub tree.

\begin{itemize}
\item If $\Delta \geq 0$ and $\Delta' \geq 0$, it means that the height
of right sub tree isn't less than the height of left sub tree both
before insertion and after insertion. In this case, the increment in
height of the tree is only `contributed' from the right sub tree, which
is $\Delta H_r$.

\item If $\Delta \leq 0$, which means the height of left sub tree isn't
less than the height of right sub tree before, and it becomes
$\Delta' \geq 0$,
which means that the height of right sub tree increases due to insertion,
and the left side keeps same ($|L'|=|L|$). So the increment in height is
\[
\begin{array}{rll}
\Delta H & = max(|R'|, |L'|) - max (|R|, |L|) & \{\Delta \leq 0 \land \Delta' \geq 0 \}\\
         & = |R'|-|L| & \{|L|=|L'| \}\\
         & = |R|+\Delta H_r - |L| & \\
         & = \Delta + \Delta H_r &
\end{array}
\]

\item For the case $\Delta \geq 0$ and $\Delta' \leq 0$, Similar as the
second one, we can get.

\[
\begin{array}{rll}
\Delta H & = max(|R'|, |L'|) - max (|R|, |L|) & \{\Delta \geq 0 \land \Delta' \leq 0 \}\\
         & = |L'|-|R| & \\
         & = |L|+\Delta H_l - |R| & \\
         & = \Delta H_l - \Delta&
\end{array}
\]

\item For the last case, the both $\Delta$ and $\Delta'$ is no bigger than
zero, which means the height left sub tree is always greater than or equal
 to the right sub tree, so the increment in height is only `contributed'
from the left sub tree, which is $\Delta H_l$.
\end{itemize}

The next problem in front of us is how to determine the new balancing
factor value $\Delta'$ before performing balancing adjustment.
According to the definition of AVL tree, the balancing factor is the
height of right sub tree minus the height of left sub tree. We have
the following facts.

\be
\begin{array}{rl}
\Delta' & = |R'| - |L'| \\
        & = |R| + \Delta H_r - (|L| + \Delta H_l) \\
        & = |R| - |L| + \Delta H_r - \Delta H_l \\
        & = \Delta + \Delta H_r - \Delta H_l
\end{array}
\ee

With all these changes in height and balancing factor get clear, it's
possible to define the $tree()$ function mentioned in (\ref{eq:ins}).

\be
tree((L', \Delta H_l), Key, (R', \Delta H_r), \Delta) =
  balance (node(L', Key, R', \Delta'), \Delta H)
\ee

Before we moving into details of balancing adjustment, let's translate
the above equations to real programs in Haskell.

First is the insert function.

\lstset{language=Haskell}
\begin{lstlisting}
insert::(Ord a)=>AVLTree a -> a -> AVLTree a
insert t x = fst $ ins t where
    ins Empty = (Br Empty x Empty 0, 1)
    ins (Br l k r d)
        | x < k     = tree (ins l) k (r, 0) d
        | x == k    = (Br l k r d, 0)
        | otherwise = tree (l, 0) k (ins r) d
\end{lstlisting} %$

Here we also handle the case that inserting a duplicated key (which
means the key has already existed.) as just overwriting.

\begin{lstlisting}
tree::(AVLTree a, Int) -> a -> (AVLTree a, Int) -> Int -> (AVLTree a, Int)
tree (l, dl) k (r, dr) d = balance (Br l k r d', delta) where
    d' = d + dr - dl
    delta = deltaH d d' dl dr
\end{lstlisting}

And the definition of height increment is as below.

\begin{lstlisting}
deltaH :: Int -> Int -> Int -> Int -> Int
deltaH d d' dl dr
       | d >=0 && d' >=0 = dr
       | d <=0 && d' >=0 = d+dr
       | d >=0 && d' <=0 = dl - d
       | otherwise = dl
\end{lstlisting}

\subsection{Balancing adjustment}
\index{AVL tree!balancing}
As the pattern matching approach is adopted in doing re-balancing.
We need consider what kind of patterns violate the AVL tree property.

Figure \ref{fig:insert-fix} shows the 4 cases which need fix. For all
these 4 cases the balancing factors are either -2, or +2 which exceed
the range of $[-1, 1]$. After balancing adjustment, this factor turns
to be 0, which means the height of left sub tree is equal to the right
sub tree.

\begin{figure}[htbp]
   \begin{center}
     \setlength{\unitlength}{1cm}
     \begin{picture}(15, 15)
        % arrows
        \put(4.5, 9.5){\vector(1, -1){1}}
        \put(4.5, 5){\vector(1, 1){1}}
        \put(10, 9.5){\vector(-1, -1){1}}
        \put(10, 5){\vector(-1, 1){1}}
        % delta values
        \put(5, 13){$\delta(z) = -2$}
        \put(2.5, 12){$\delta(y) = -1$}
        \put(10, 13){$\delta(x) = 2$}
        \put(11.5, 11.5){$\delta(y) = 1$}
        \put(1.5, 5.5){$\delta(z) = -2$}
        \put(3.5, 4){$\delta(x) = 1$}
        \put(12, 5.5){$\delta(x) = 2$}
        \put(10.5, 4){$\delta(z) = -1$}
        \put(7.5, 10){$\delta'(y) = 0$}
        % graphics
	\put(0, 7){\includegraphics[scale=0.5]{img/insert-ll.ps}}
        \put(0, 0){\includegraphics[scale=0.5]{img/insert-lr.ps}}
        \put(7, 7){\includegraphics[scale=0.5]{img/insert-rr.ps}}
        \put(8.5, 0){\includegraphics[scale=0.5]{img/insert-rl.ps}}
        \put(2, 5){\includegraphics[scale=0.5]{img/insert-fixed.ps}}
      \end{picture}
     \caption{4 cases for balancing a AVL tree after insertion} \label{fig:insert-fix}
  \end{center}
\end{figure}

We call these four cases left-left lean, right-right lean, right-left lean,
and left-right lean cases in clock-wise direction from top-left. We denote
the balancing factor before fixing as $\delta(x), \delta(y)$, and $\delta(z)$, while after fixing, they changes to $\delta'(x), \delta'(y)$, and
$\delta'(z)$ respectively.

We'll next prove that, after fixing, we have $\delta(y)=0$ for all
four cases, and we'll provide the result values of $\delta'(x)$ and
$\delta'(z)$.

\subsubsection*{Left-left lean case}

As the structure of sub tree $x$ doesn't change due to fixing, we immediately get
$\delta'(x) = \delta(x)$.

Since $\delta(y) = -1$ and $\delta(z) = -2$, we have

\be
  \begin{array}{l}
  \delta(y) = |C| - |x| = -1 \Rightarrow |C| = |x| - 1 \\
  \delta(z) = |D| - |y| = -2 \Rightarrow |D| = |y| - 2
  \end{array}
  \label{eq:ll-cd}
\ee

After fixing.

\be
  \begin{array}{rll}
  \delta'(z) & = |D| - |C| & \{ From (\ref{eq:ll-cd}) \}\\
             & = |y| - 2 - (|x| - 1) & \\
             & = |y| - |x| - 1 & \{  x \text{ is child of } y \Rightarrow |y|-|x| = 1\} \\
             & = 0 &
  \end{array}
  \label{eq:ll-delta-z}
\ee

For $\delta'(y)$, we have the following fact after fixing.

\be
  \begin{array}{rll}
  \delta'(y) & = |z| - |x| & \\
             & = 1 + max(|C|, |D|) - |x| & \{ \text{By (\ref{eq:ll-delta-z}), we have} |C| = |D|\} \\
             & = 1 + |C| - |x| & \{ \text{By (\ref{eq:ll-cd})}\} \\
             & = 1 + |x| - 1 - |x| & \\
             & = 0 &
  \end{array}
\ee

Summarize the above results, the left-left lean case adjust the balancing
factors as the following.

\be
  \begin{array}{l}
  \delta'(x) = \delta(x) \\
  \delta'(y) = 0 \\
  \delta'(z) = 0
  \end{array}
\ee

\subsubsection*{Right-right lean case}

Since right-right case is symmetric to left-left case, we can easily achieve the result balancing factors as

\be
  \begin{array}{l}
  \delta'(x) = 0 \\
  \delta'(y) = 0 \\
  \delta'(z) = \delta(z)
  \end{array}
  \label{eq:rr-result}
\ee

\subsubsection*{Right-left lean case}

First let's consider $\delta'(x)$. After balance fixing, we have.

\be
  \delta'(x) = |B| - |A|
  \label{eq:rl-dx}
\ee

Before fixing, if we calculate the height of $z$, we can get.

\be
  \begin{array}{rll}
  |z| & = 1 + max(|y|, |D|) &  \{ \delta(z) = -1 \Rightarrow |y| > |D|\} \\
      & = 1 + |y| & \\
      & = 2 + max(|B|, |C|)
  \end{array}
  \label{eq:rl-z}
\ee

While since $\delta(x) = 2$, we can deduce that.

\be
  \begin{array}{rll}
  \delta(x) = 2 & \Rightarrow |z| - |A| = 2 & \{ \text{By (\ref{eq:rl-z})} \}\\
                & \Rightarrow 2 + max(|B|, |C|) - |A| = 2 & \\
                & \Rightarrow max(|B|, |C|) - |A| = 0 &
  \end{array}
  \label{eq:rl-ca}
\ee

If $\delta(y) = 1$, which means $|C| - |B| = 1$, it means

\be
  max(|B|, |C|)= |C| = |B|+1
\ee

Take this into (\ref{eq:rl-ca}) yields

\be
  \begin{array}{ll}
  |B|+1-|A| = 0 \Rightarrow |B|-|A|= -1 & \{ \text{By (\ref{eq:rl-dx}) } \} \\
  \Rightarrow \delta'(x) = -1 &
  \end{array}
\ee

If $\delta(y) \neq 1$, it means $max(|B|, |C|) = |B|$, taking this into
(\ref{eq:rl-ca}), yields.

\be
  \begin{array}{ll}
  |B| - |A| = 0  & \{ \text{By (\ref{eq:rl-dx})} \} \\
  \Rightarrow \delta'(x) = 0 &
  \end{array}
\ee

Summarize these 2 cases, we get relationship of $\delta'(x)$ and
$\delta(y)$ as the following.

\be
\delta'(x) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  -1 & \delta(y) = 1 \\
  0 & otherwise
  \end{array}
\right.
\label{eq:rl-dx-dy}
\ee

For $\delta'(z)$ according to definition, it is equal to.

\be
  \begin{array}{rll}
    \delta'(z) & = |D| - |C| & \{ \delta(z) = -1 = |D| - |y| \} \\
               & = |y| - |C| - 1 & \{ |y| = 1 + max(|B|, |C|) \} \\
               & = max(|B|, |C|) - |C|
  \end{array}
  \label{eq:rl-dz}
\ee

If $\delta(y) = -1$, then we have $|C| - |B| = -1$, so $max(|B|, |C|) = |B| = |C| + 1$. Takes this into (\ref{eq:rl-dz}), we get $\delta'(z) = 1$.

If $\delta(y) \neq -1$, then $max(|B|, |C|) = |C|$, we get $\delta'(z)=0$.

Combined these two cases, the relationship between $\delta'(z)$ and $\delta(y)$ is as below.

\be
\delta'(z) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  1 & \delta(y) = -1 \\
  0 & otherwise
  \end{array}
  \right.
  \label{eq:rl-dz-dy}
\ee

Finally, for $\delta'(y)$, we deduce it like below.

\be
  \begin{array}{rl}
  \delta'(y) & = |z| - |x| \\
             & = max(|C|, |D|) - max(|A|, |B|)
  \end{array}
  \label{eq:rl-dy}
\ee

There are three cases.
\begin{itemize}

\item If $\delta(y)=0$, it means $|B|=|C|$, and according to (\ref{eq:rl-dx-dy}) and (\ref{eq:rl-dz-dy}), we have $\delta'(x)=0 \Rightarrow |A| = |B|$, and $\delta'(z)=0 \Rightarrow |C|=|D|$, these lead to $\delta'(y)=0$.

\item If $\delta(y)=1$, From (\ref{eq:rl-dz-dy}), we have $\delta'(z)=0 \Rightarrow |C| = |D|$.
\[
  \begin{array}{rll}
  \delta'(y) & = max(|C|, |D|) - max(|A|, |B|) & \{|C|=|D|\} \\
             & = |C| - max(|A|, |B|) & \{\text{From (\ref{eq:rl-dx-dy}): $\delta'(x)=-1 \Rightarrow |B|-|A|=-1$} \} \\
             & = |C| - (|B| + 1) & \{ \delta(y) = 1 \Rightarrow |C|-|B|=1\} \\
             & = 0
  \end{array}
\]

\item If $\delta(y)=-1$, From (\ref{eq:rl-dx-dy}), we have $\delta'(x)=0 \Rightarrow |A|=|B|$.
\[
  \begin{array}{rll}
  \delta'(y) & = max(|C|, |D|) - max(|A|, |B|) & \{|A|=|B|\} \\
             & = max(|C|, |D|) - |B| & \{ \text{From (\ref{eq:rl-dz-dy}): $|D|-|C|=1$} \} \\
             & = |C| + 1 - |B| & \{  \delta(y) = -1 \Rightarrow |C|-|B|=-1\} \\
             & = 0
  \end{array}
\]

\end{itemize}

All three cases lead to the same result that $\delta'(y)=0$.

Collect all the above results, we get the new balancing factors after fixing as the following.

\be
  \begin{array}{l}
  \delta'(x) = \left \{
    \begin{array}
    {r@{\quad:\quad}l}
    -1 & \delta(y) = 1 \\
    0 & otherwise
    \end{array}
    \right. \\
  \delta'(y) = 0 \\
  \delta'(z) = \left \{
    \begin{array}
    {r@{\quad:\quad}l}
    1 & \delta(y) = -1 \\
    0 & otherwise
    \end{array}
    \right.
  \end{array}
  \label{eq:rl-result}
\ee

\subsubsection*{Left-right lean case}

Left-right lean case is symmetric to the Right-left lean case. By using
the similar deduction, we can find the new balancing factors are identical
to the result in (\ref{eq:rl-result}).

\subsection{Pattern Matching}
All the problems have been solved and it's time to define the final
pattern matching fixing function.

\be
balance(T, \Delta H) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  (((A, x, B, \delta(x)), y, (C, z, D, 0), 0), 0) & P_{ll}(T) \\
  (((A, x, B, 0), y, (C, z, D, \delta(z)), 0), 0) & P_{rr}(T) \\
  (((A, x, B, \delta'(x)), y, (C, z, D, \delta'(z)), 0), 0) & P_{rl}(T) \lor P_{lr}(T) \\
  (T, \Delta H) & otherwise
  \end{array}
\right.
\ee

Where $P_{ll}(T)$ means the pattern of tree $T$ is left-left lean respectively. $\delta'(x)$ and $delta'(z)$ are defined in (\ref{eq:rl-result}). The four patterns are tested as below.

\be
\begin{array}{l}
P_{ll}(T): T = (((A, x, B, \delta(x)), y, C, -1), z, D, -2) \\
P_{rr}(T): T = (A, x, (B, y, node(C, z, D, \delta(z)), 1), 2) \\
P_{rl}(T): T = ((A, x, (B, y, C, \delta(y)), 1), z, D, -2) \\
P_{lr}(T): T = (A, x, ((B, y, C, \delta(y)), z, D, -1), 2)
\end{array}
\ee

Translating the above function definition to Haskell yields a simple
and intuitive program.

\begin{lstlisting}
balance (Br (Br (Br a x b dx) y c (-1)) z d (-2), _) =
        (Br (Br a x b dx) y (Br c z d 0) 0, 0)
balance (Br a x (Br b y (Br c z d dz)    1)    2, _) =
        (Br (Br a x b 0) y (Br c z d dz) 0, 0)
balance (Br (Br a x (Br b y c dy)    1) z d (-2), _) =
        (Br (Br a x b dx') y (Br c z d dz') 0, 0) where
    dx' = if dy ==  1 then -1 else 0
    dz' = if dy == -1 then  1 else 0
balance (Br a x (Br (Br b y c dy) z d (-1))    2, _) =
        (Br (Br a x b dx') y (Br c z d dz') 0, 0) where
    dx' = if dy ==  1 then -1 else 0
    dz' = if dy == -1 then  1 else 0
balance (t, d) = (t, d)
\end{lstlisting}

The insertion algorithm takes time proportion to the height of the
tree, and according to the result we proved above, its performance
is $O(\lg n)$ where $n$ is the number of elements stored in the AVL
tree.

\subsubsection{Verification}
\index{AVL tree!verification}
One can easily create a function to verify a tree is AVL tree.
Actually we need verify two things, first, it's a binary search tree;
second, it satisfies AVL tree property.

We left the first verification problem as an exercise to the reader.

In order to test if a binary tree satisfies AVL tree property, we can
test the difference in height between its two children, and recursively
test that both children conform to AVL property until we arrive at
an empty leaf.

\be
  avl?(T) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  True & T = \phi \\
  avl?(L) \land avl?(R) \land ||R|-|L|| \leq 1 & otherwise
  \end{array}
  \right .
\ee

And the height of a AVL tree can also be calculate from the definition.

\be
  |T| = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  0 & T = \phi \\
  1 + max(|R|, |L|) & otherwise
  \end{array}
  \right .
\ee

The corresponding Haskell program is given as the following.

\begin{lstlisting}
isAVL :: (AVLTree a) -> Bool
isAVL Empty = True
isAVL (Br l _ r d) = and [isAVL l, isAVL r, abs (height r - height l) <= 1]

height :: (AVLTree a) -> Int
height Empty = 0
height (Br l _ r _) = 1 + max (height l) (height r)
\end{lstlisting}

\begin{Exercise}
Write a program to verify a binary tree is a binary search tree in your
favorite programming language. If you choose to use an imperative language,
please consider realize this program without recursion.
\end{Exercise}



% ================================================================
%                 Deletion
% ================================================================

\section{Deletion}
\index{AVL tree!deletion}

As we mentioned before, deletion doesn't make significant sense in
purely functional settings. As the tree is read only, it's typically
performs frequently looking up after build.

Even if we implement deletion, it's actually re-building the tree
as we presented in chapter of red-black tree. We left the deletion
of AVL tree as an exercise to the reader.

\begin{Exercise}

\begin{itemize}

\item Take red-black tree deletion algorithm as an example, write the
AVL tree deletion program in purely functional approach in your
favorite programming language.
\end{itemize}

\end{Exercise}

\section{Imperative AVL tree algorithm $\star$}
\index{AVL tree!imperative insertion}

We almost finished all the content in this chapter about AVL tree.
However, it necessary to show the traditional insert-and-rotate
approach as the comparator to pattern matching algorithm.

Similar as the imperative red-black tree algorithm, the strategy
is first to do the insertion as same as for binary search tree,
then fix the balance problem by rotation and return the final result.

\begin{algorithmic}[1]
\Function{Insert}{$T, k$}
  \State $root \gets T$
  \State $x \gets$ \Call{Create-Leaf}{$k$}
  \State \Call{$\delta$}{$x$} $\gets 0$
  \State $parent \gets$ NIL
  \While{$T \neq$ NIL}
    \State $parent \gets T$
    \If{$k <$ \Call{Key}{$T$}}
      \State $T \gets $ \Call{Left}{$T$}
    \Else
      \State $T \gets $ \Call{Right}{$T$}
    \EndIf
  \EndWhile
  \State \Call{Parent}{$x$} $\gets parent$
  \If{$parent =$ NIL} \Comment{tree $T$ is empty}
    \State \Return $x$
  \ElsIf{$k <$ \Call{Key}{$parent$}}
    \State \Call{Left}{$parent$} $\gets x$
  \Else
    \State \Call{Right}{$parent$} $\gets x$
  \EndIf
  \State \Return \Call{AVL-Insert-Fix}{$root, x$}
\EndFunction
\end{algorithmic}

Note that after insertion, the height of the tree may increase, so that
the balancing factor $\delta$ may also change, insert on right side will
increase $\delta$ by 1, while insert on left side will decrease it. By
the end of this algorithm, we need perform bottom-up fixing from node $x$
towards root.

We can translate the pseudo code to real programming language, such as
Python \footnote{C and C++ source code are available along with this book}.
\lstset{language=Python}
\begin{lstlisting}
def avl_insert(t, key):
    root = t
    x = Node(key)
    parent = None
    while(t):
        parent = t
        if(key < t.key):
            t = t.left
        else:
            t = t.right
    if parent is None: #tree is empty
        root = x
    elif key < parent.key:
        parent.set_left(x)
    else:
        parent.set_right(x)
    return avl_insert_fix(root, x)
\end{lstlisting}

This is a top-down algorithm. It searches the tree from root down to the proper
position and inserts the new key as a leaf. By the end of this algorithm, it calls fixing procedure, by passing the root and the new node inserted.

Note that we reuse the same methods of \texttt{set\_left()} and \texttt{set\_right()} as
we defined in chapter of red-black tree.

In order to resume the AVL tree balance property by fixing, we first determine if the new node is inserted on left hand or right hand. If it is on left, the balancing factor $\delta$ decreases, otherwise it increases. If we denote the new value as $\delta'$, there are 3 cases of the relationship between $\delta$ and $\delta'$.

\begin{itemize}
\item If $|\delta| = 1$ and $|\delta'| = 0$, this means adding the new node makes the tree perfectly balanced, the height of the parent node doesn't change, the algorithm can be terminated.

\item If $|\delta| = 0$ and $|\delta'| = 1$, it means that either the height of left sub tree or right sub tree increases, we need go on check the upper level of the tree.

\item If $|\delta| = 1$ and $|\delta'| = 2$, it means the AVL tree property is violated due to the new insertion. We need perform rotation to fix it.
\end{itemize}

\begin{algorithmic}[1]
\Function{AVL-Insert-Fix}{$T, x$}
  \While{\Call{Parent}{$x$} $\neq$ NIL}
    \State $\delta \gets $ \textproc{$\delta$}(\Call{Parent}{$x$})
    \If{$x = $ \textproc{Left}(\Call{Parent}{$x$})}
      \State $\delta' \gets \delta - 1$
    \Else
      \State $\delta' \gets \delta + 1$
    \EndIf
    \State \textproc{$\delta$}(\Call{Parent}{$x$}) $\gets \delta'$
    \State $P \gets $ \Call{Parent}{$x$}
    \State $L \gets $ \Call{Left}{$x$}
    \State $R \gets $ \Call{Right}{$x$}
    \If{$|\delta| = 1$ and $|\delta'| = 0$} \Comment{Height doesn't change, terminates.}
      \State \Return $T$
    \ElsIf{$|\delta| = 0$ and $|\delta'| = 1$} \Comment{Go on bottom-up updating.}
      \State $x \gets P$
    \ElsIf{$|\delta| = 1$ and $|\delta'| = 2$}
      \If{$\delta'=2$}
        \If{$\delta(R) = 1$} \Comment{Right-right case}
          \State $\delta(P) \gets 0$ \Comment{By (\ref{eq:rr-result})}
          \State $\delta(R) \gets 0$
          \State $T \gets $ \Call{Left-Rotate}{$T, P$}
        \EndIf
        \If{$\delta(R) = -1$} \Comment{Right-left case}
          \State $\delta_y \gets $ \textproc{$\delta$}(\Call{Left}{$R$}) \Comment{By (\ref{eq:rl-result})}
          \If{$\delta_y = 1$}
            \State $\delta(P) \gets -1$
          \Else
            \State $\delta(P) \gets 0$
          \EndIf
          \State \textproc{$\delta$}(\Call{Left}{$R$}) $\gets 0$
          \If{$\delta_y = -1$}
            \State $\delta(R) \gets 1$
          \Else
            \State $\delta(R) \gets 0$
          \EndIf
          \State $T \gets $ \Call{Right-Rotate}{$T, R$}
          \State $T \gets $ \Call{Left-Rotate}{$T, P$}
        \EndIf
      \EndIf
      \If{$\delta' = -2$}
        \If{$\delta(L) = -1$} \Comment{Left-left case}
          \State $\delta(P) \gets 0$
          \State $\delta(L) \gets 0$
          \State \Call{Right-Rotate}{$T, P$}
        \Else \Comment{Left-Right case}
          \State $\delta_y \gets $ \textproc{$\delta$}(\Call{Right}{$L$})
          \If{$\delta_y = 1$}
            \State $\delta(L) \gets -1$
          \Else
            \State $\delta(L) \gets 0$
          \EndIf
          \State \textproc{$\delta$}(\Call{Right}{$L$}) $\gets 0$
          \If{$\delta_y = -1$}
            \State $\delta(P) \gets 1$
          \Else
            \State $\delta(P) \gets 0$
          \EndIf
          \State \Call{Left-Rotate}{$T, L$}
          \State \Call{Right-Rotate}{$T, P$}
        \EndIf
      \EndIf
      \State break
    \EndIf
  \EndWhile
  \State \Return $T$
\EndFunction
\end{algorithmic}

Here we reuse the rotation algorithms mentioned in red-black tree chapter.
Rotation operation doesn't update balancing factor $\delta$ at all,
However, since rotation changes (actually improves) the balance situation
we should update these factors. Here we refer the results from above section. Among the four cases, right-right case and left-left case only need one rotation, while right-left case and left-right case need two rotations.

The relative python program is shown as the following.

\begin{lstlisting}
def avl_insert_fix(t, x):
    while x.parent is not None:
        d2 = d1 = x.parent.delta
        if x == x.parent.left:
            d2 = d2 - 1
        else:
            d2 = d2 + 1
        x.parent.delta = d2
        (p, l, r) = (x.parent, x.parent.left, x.parent.right)
        if abs(d1) == 1 and abs(d2) == 0:
            return t
        elif abs(d1) == 0 and abs(d2) == 1:
            x = x.parent
        elif abs(d1)==1 and abs(d2) == 2:
            if d2 == 2:
                if r.delta == 1:  # Right-right case
                    p.delta = 0
                    r.delta = 0
                    t = left_rotate(t, p)
                if r.delta == -1: # Right-Left case
                    dy = r.left.delta
                    if dy == 1:
                        p.delta = -1
                    else:
                        p.delta = 0
                    r.left.delta = 0
                    if dy == -1:
                        r.delta = 1
                    else:
                        r.delta = 0
                    t = right_rotate(t, r)
                    t = left_rotate(t, p)
            if d2 == -2:
                if l.delta == -1: # Left-left case
                    p.delta = 0
                    l.delta = 0
                    t = right_rotate(t, p)
                if l.delta == 1: # Left-right case
                    dy = l.right.delta
                    if dy == 1:
                        l.delta = -1
                    else:
                        l.delta = 0
                    l.right.delta = 0
                    if dy == -1:
                        p.delta = 1
                    else:
                        p.delta = 0
                    t = left_rotate(t, l)
                    t = right_rotate(t, p)
            break
    return t
\end{lstlisting}

We skip the AVL tree deletion algorithm and left this as an exercise to the reader.

\begin{Exercise}

\begin{itemize}
\item Write the deletion algorithm in imperative approach in your favorite
programming language.

\end{itemize}

\end{Exercise}


\section{Chapter note}
AVL tree was invented in 1962 by Adelson-Velskii and Landis\cite{wiki},
\cite{TFATP}. The name AVL tree comes from the two inventor's name. It's earlier than red-black tree.

It's very common to compare AVL tree and red-black tree, both are self-balancing binary search trees, and for all the major operations, they both consume $O(\lg n)$ time. From the result of (\ref{eq:AVL-height}), AVL tree is more rigidly balanced hence they are faster than red-black tree in looking up intensive applications \cite{wiki}. However, red-black trees could perform better in frequently insertion and removal cases.

Many popular self-balancing binary search tree libraries are implemented on top of red-black tree such as STL etc. However, AVL tree provides an intuitive and effective solution to the balance problem as well.

After this chapter, we'll extend the tree data structure from storing data in node to storing information on edges, which leads to Trie and Patrica, etc. If we extend the number of children from two to more, we can get B-tree. These data structures will be introduced next.

\begin{thebibliography}{99}

\bibitem{hackage}
Data.Tree.AVL http://hackage.haskell.org/packages/archive/AvlTree/4.2/doc/html/Data-Tree-AVL.html

\bibitem{okasaki}
Chris Okasaki. ``FUNCTIONAL PEARLS Red-Black Trees in a Functional Setting''. J. Functional Programming. 1998

\bibitem{wiki}
Wikipedia. ``AVL tree''. http://en.wikipedia.org/wiki/AVL\_tree

\bibitem{TFATP}
Guy Cousinear, Michel Mauny. ``The Functional Approach to Programming''. Cambridge University Press; English Ed edition (October 29, 1998). ISBN-13: 978-0521576819

\bibitem{py-avl}
Pavel Grafov. ``Implementation of an AVL tree in Python''. http://github.com/pgrafov/python-avl-tree
\end{thebibliography}

\ifx\wholebook\relax\else
\end{document}
\fi

% LocalWords:  AVL Okasaki STL
